Class LinkedList<T>

A list collection class based on a doubly linked list data structure.

Implements

IEnumerable<T>, System.Collections.IEnumerable, System.IFormattable, System.ICloneable, System.IDisposable, System.Collections.Generic.IList<T>, System.Collections.Generic.ICollection<T>, ICollection<T>, ICollectionValue<T>, IDirectedCollectionValue<T>, IDirectedEnumerable<T>, IExtensible<T>, IIndexed<T>, IList<T>, IQueue<T>, ISequenced<T>, IShowable, IStack<T>

Bases

object, EnumerableBase<T>, CollectionValueBase<T>, CollectionBase<T>, DirectedCollectionBase<T>, SequencedBase<T>

Field overview

isReadOnlyBase, Inherited from CollectionBase<T> ,
itemequalityComparer, Inherited from CollectionBase<T> ,
size, Inherited from CollectionBase<T> ,
stamp, Inherited from CollectionBase<T>

Event overview

CollectionChanged, Inherited from CollectionValueBase<T> ,
CollectionCleared, Inherited from CollectionValueBase<T> ,
ItemInserted, Inherited from CollectionValueBase<T> ,
ItemRemovedAt, Inherited from CollectionValueBase<T> ,
ItemsAdded, Inherited from CollectionValueBase<T> ,
ItemsRemoved, Inherited from CollectionValueBase<T>

Property overview

ActiveEvents, Inherited from CollectionValueBase<T> ,
AllowsDuplicates ,
ContainsSpeed ,
Count ,
CountSpeed, Inherited from CollectionBase<T> ,
Direction, Inherited from SequencedBase<T> ,
DuplicatesByCounting ,
EqualityComparer, Inherited from CollectionBase<T> ,
FIFO ,
First ,
IndexingSpeed ,
IsEmpty, Inherited from CollectionBase<T> ,
IsFixedSize ,
IsReadOnly, Inherited from CollectionBase<T> ,
IsValid ,
this[int index] ,
this[int start, int count] ,
Last ,
ListenableEvents ,
Offset ,
SyncRoot, Inherited from CollectionBase<T> ,
Underlying

Constructor overview

LinkedList<T>(System.Collections.Generic.IEqualityComparer<T> itemequalityComparer) ,
LinkedList<T>()

Method overview

Add(T item) ,
AddAll<U>(IEnumerable<U> items) ,
All(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Apply(Act<T> action), Inherited from CollectionValueBase<T> ,
Backwards() ,
Check() ,
checkRange(int start, int count), Inherited from CollectionBase<T> ,
Choose() ,
Clear() ,
Clone() ,
Contains(T item) ,
ContainsAll<U>(IEnumerable<U> items) ,
ContainsCount(T item) ,
CopyTo(T[] array, int index), Inherited from CollectionValueBase<T> ,
Dequeue() ,
Dispose() ,
Enqueue(T item) ,
Equals(object obj), Inherited from object ,
Exists(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Filter(Fun<T,bool> filter) ,
Finalize(), Inherited from object ,
Find(ref T item) ,
Find(Fun<T,bool> predicate, out T item), Inherited from CollectionValueBase<T> ,
FindAll(Fun<T,bool> filter) ,
FindIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindLast(Fun<T,bool> predicate, out T item), Inherited from DirectedCollectionBase<T> ,
FindLastIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindOrAdd(ref T item) ,
GetEnumerator() ,
GetHashCode(), Inherited from object ,
GetSequencedHashCode() ,
GetType(), Inherited from object ,
GetUnsequencedHashCode() ,
IndexOf(T item) ,
Insert(int i, T item) ,
Insert(IList<T> pointer, T item) ,
InsertAll<U>(int i, IEnumerable<U> items) ,
InsertFirst(T item) ,
InsertLast(T item) ,
IsSorted() ,
IsSorted(System.Collections.Generic.IComparer<T> c) ,
ItemMultiplicities() ,
LastIndexOf(T item) ,
LastViewOf(T item) ,
Map<V>(Fun<T,V> mapper) ,
Map<V>(Fun<T,V> mapper, System.Collections.Generic.IEqualityComparer<V> equalityComparer) ,
MemberwiseClone(), Inherited from object ,
modifycheck(int stamp) ,
Pop() ,
Push(T item) ,
raiseCollectionChanged(), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count, System.Nullable<int> offset), Inherited from CollectionValueBase<T> ,
raiseForAdd(T item), Inherited from CollectionValueBase<T> ,
raiseForInsert(int i, T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item, int count), Inherited from CollectionValueBase<T> ,
raiseForRemoveAll(ICollectionValue<T> wasRemoved), Inherited from CollectionValueBase<T> ,
raiseForRemoveAt(int index, T item), Inherited from CollectionValueBase<T> ,
raiseForSetThis(int index, T value, T item), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem, int count), Inherited from CollectionValueBase<T> ,
raiseItemInserted(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemRemovedAt(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemsAdded(T item, int count), Inherited from CollectionValueBase<T> ,
raiseItemsRemoved(T item, int count), Inherited from CollectionValueBase<T> ,
Remove() ,
Remove(T item) ,
Remove(T item, out T removeditem) ,
RemoveAll<U>(IEnumerable<U> items) ,
RemoveAllCopies(T item) ,
RemoveAt(int i) ,
RemoveFirst() ,
RemoveInterval(int start, int count) ,
RemoveLast() ,
RetainAll<U>(IEnumerable<U> items) ,
Reverse() ,
SequencedEquals(ISequenced<T> that) ,
Show(System.Text.StringBuilder stringbuilder, ref int rest, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
Shuffle() ,
Shuffle(System.Random rnd) ,
Slide(int offset) ,
Slide(int offset, int size) ,
Sort() ,
Sort(System.Collections.Generic.IComparer<T> c) ,
Span(IList<T> otherView) ,
ToArray(), Inherited from CollectionValueBase<T> ,
ToString(string format, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
ToString(), Inherited from CollectionValueBase<T> ,
TrySlide(int offset) ,
TrySlide(int offset, int size) ,
UniqueItems() ,
UnsequencedEquals(ICollection<T> that) ,
Update(T item) ,
Update(T item, out T olditem) ,
updatecheck() ,
UpdateOrAdd(T item) ,
UpdateOrAdd(T item, out T olditem) ,
View(int start, int count) ,
ViewOf(T item)

Property details

bool AllowsDuplicatesAccess: Read-Only

Value:True since this collection has bag semantics.

Speed ContainsSpeedAccess: Read-Only

Value:Speed.Linear

The value is symbolic indicating the type of asymptotic complexity in terms of the size of this collection (worst-case or amortized as relevant).
int CountAccess: Read-Only

Value:The number of items in this collection

bool DuplicatesByCountingAccess: Read-Only

Value:True if only one representative of a group of equal items is kept in the collection together with the total count.

By convention this is true for any collection with set semantics.
bool FIFOAccess: Read-Write

Value:True if the Remove() operation removes from the start of the list, false if it removes from the end. THe default for a new linked list is true.

Since Add(T item) always add at the end of the list, this describes if list has FIFO or LIFO semantics.
T FirstAccess: Read-Only

Value:The first item in this list.

Throws
NoSuchItemException if this list is empty.
Speed IndexingSpeedAccess: Read-Only

Value:

bool IsFixedSizeAccess: Read-Only
bool IsValidAccess: Read-Only

Value:

T this[int index]Access: Read-Write

Value:The i'th item of this list.

On this list, this indexer is read/write. /ThrowsSystem.IndexOutOfRangeException if i is negative or >= the size of the collection.
Parameters:
index:The index of the item to fetch or store.
F IDirectedCollectionValue<T> this[int start, int count]Access: Read-Only

Value:The directed collection of items in a specific index interval.

/ThrowsSystem.IndexOutOfRangeException.
Parameters:
start:The low index of the interval (inclusive).
count:The size of the range.
T LastAccess: Read-Only

Value:The last item in this list.

Throws
NoSuchItemException if this list is empty.
EventTypeEnum ListenableEventsAccess: Read-Only

Value:

int OffsetAccess: Read-Only

Value:Offset for this list view or 0 for a underlying list.

IList<T> UnderlyingAccess: Read-Only

Value:Underlying list for view.

Null if this list is not a view.

Constructor details

LinkedList<T>(System.Collections.Generic.IEqualityComparer<T> itemequalityComparer) Create a linked list with en external item equalityComparer
Parameters:
itemequalityComparer:The external equalityComparer
LinkedList<T>() Create a linked list with the natural item equalityComparer

Method details

bool Add(T item) Add an item to this collection if possible.
Returns:True.
Parameters:
item:The item to add.
void AddAll<U>(IEnumerable<U> items) Add the elements from another collection with a more specialized item type to this collection.
Type parameters:
UThe type of items to add
Constraints:
U : T
Parameters:
items:The items to add
IDirectedCollectionValue<T> Backwards() Create a collection containing the same items as this collection, but whose enumerator will enumerate the items backwards. The new collection will become invalid if the original is modified. Method typicaly used as in foreach (T x in coll.Backwards()) {...}
Returns:The backwards collection.
bool Check() Check the sanity of this list
Returns:true if sane
T Choose() Choose some item of this collection.
Throws
NoSuchItemExceptionif collection is empty.
Returns:
void Clear() Remove all items from this collection.
object Clone() Make a shallow copy of this LinkedList.
Returns:
bool Contains(T item) Check if this collection contains (an item equivalent to according to the itemequalityComparer) a particular value.
Returns:True if the items is in this collection.
Parameters:
item:The value to check for.
bool ContainsAll<U>(IEnumerable<U> items) Check if this collection contains all the values in another collection with respect to multiplicities.
Type parameters:
U
Constraints:
U : T
Returns:True if all values in itemsis in this collection.
Parameters:
items:The
int ContainsCount(T item) Count the number of items of the collection equal to a particular value. Returns 0 if and only if the value is not in the collection.
Returns:The number of copies found.
Parameters:
item:The value to count.
T Dequeue() Dequeue an item from the front of the queue.
Returns:The item
void Dispose() Invalidate this list. If a view, just invalidate the view. If not a view, invalidate the list and all views on it.
void Enqueue(T item) Enqueue an item at the back of the queue.
Parameters:
item:The item
IEnumerable<T> Filter(Fun<T,bool> filter) Create an enumerable, enumerating the items of this collection that satisfies a certain condition.
Returns:The filtered enumerable
Parameters:
filter:The T->bool filter delegate defining the condition
bool Find(ref T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, return in the ref argument (a binary copy of) the actual value found.
Returns:True if the items is in this collection.
Parameters:
item:The value to look for.
F IList<T> FindAll(Fun<T,bool> filter) Create a new list consisting of the items of this list satisfying a certain predicate.
Returns:The new list.
Parameters:
filter:The filter delegate defining the predicate.
bool FindOrAdd(ref T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, return in the ref argument (a binary copy of) the actual value found. Else, add the item to the collection.
Returns:True if the item was found (hence not added).
Parameters:
item:The value to look for.
System.Collections.Generic.IEnumerator<T> GetEnumerator() Create an enumerator for the collection
Returns:The enumerator
int GetSequencedHashCode()
Returns:
int GetUnsequencedHashCode() Performs a check for view validity before calling base.GetUnsequencedHashCode()
Returns:
int IndexOf(T item) Searches for an item in the list going forwrds from the start.
Returns:Index of item from start.
Parameters:
item:Item to search for.
void Insert(int i, T item) Insert an item at a specific index location in this list. /ThrowsSystem.IndexOutOfRangeException if i is negative or > the size of the collection.
Parameters:
i:The index at which to insert.
item:The item to insert.
F void Insert(IList<T> pointer, T item) Insert an item at the end of a compatible view, used as a pointer.

The pointer must be a view on the same list as this and the endpoitn of pointer must be a valid insertion point of this

Throws
IncompatibleViewExceptionIf pointer is not a view on the same list as this
System.IndexOutOfRangeException?????? if the endpoint of pointer is not inside this
DuplicateNotAllowedException if the list has AllowsDuplicates==false and the item is already in the list.
Parameters:
pointer:
item:
void InsertAll<U>(int i, IEnumerable<U> items) Insert into this list all items from an enumerable collection starting at a particular index. /ThrowsSystem.IndexOutOfRangeException if i is negative or > the size of the collection.
Type parameters:
U
Constraints:
U : T
Parameters:
i:Index to start inserting at
items:Items to insert
void InsertFirst(T item) Insert an item at the front of this list.
Parameters:
item:The item to insert.
void InsertLast(T item) Insert an item at the back of this list.
Parameters:
item:The item to insert.
F bool IsSorted() Check if this list is sorted according to the default sorting order for the item type T, as defined by the Comparer<T> class
Throws
NotComparableExceptionif T is not comparable
Returns:True if the list is sorted, else false.
bool IsSorted(System.Collections.Generic.IComparer<T> c) Check if this list is sorted according to a specific sorting order.
Returns:True if the list is sorted, else false.
Parameters:
c:The comparer defining the sorting order.
ICollectionValue<KeyValuePair<T,int>> ItemMultiplicities()
Returns:
int LastIndexOf(T item) Searches for an item in the list going backwords from the end.
Returns:Index of of item from the end.
Parameters:
item:Item to search for.
IList<T> LastViewOf(T item) Create a list view on this list containing the last occurrence of a particular item. /ThrowsSystem.ArgumentException if the item is not in this list.
Returns:The new list view.
Parameters:
item:The item to find.
F IList<V> Map<V>(Fun<T,V> mapper) Create a new list consisting of the results of mapping all items of this list.
Returns:The new list.
Parameters:
mapper:The delegate definging the map.
F IList<V> Map<V>(Fun<T,V> mapper, System.Collections.Generic.IEqualityComparer<V> equalityComparer) Create a new list consisting of the results of mapping all items of this list. The new list will use a specified equalityComparer for the item type.
Type parameters:
VThe type of items of the new list
Returns:The new list.
Parameters:
mapper:The delegate defining the map.
equalityComparer:The equalityComparer to use for the new list
P void modifycheck(int stamp) Check that the list has not been updated since a particular time.
Throws
CollectionModifiedException if check fails.
Parameters:
stamp:The stamp indicating the time.
F T Pop() Pop the item at the top of the stack from the stack.
Returns:The popped item.
F void Push(T item) Push an item to the top of the stack.
Parameters:
item:The item
T Remove() Remove one item from the list: from the front if FIFO is true, else from the back. /ThrowsC5.NoSuchItemException if this list is empty.
Returns:The removed item.
bool Remove(T item) Remove a particular item from this collection. Since the collection has bag semantics only one copy equivalent to the supplied item is removed.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
bool Remove(T item, out T removeditem) Remove a particular item from this collection if found (only one copy). If an item was removed, report a binary copy of the actual item removed in the argument.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove on input.
removeditem:The value removed.
void RemoveAll<U>(IEnumerable<U> items) Remove all items in another collection from this one, taking multiplicities into account.

Always removes from the front of the list.

The asymptotic running time complexity of this method is O(n+m+v*log(v)), where n is the size of this list, m is the size of the items collection and v is the number of views. The method will temporarily allocate memory of size O(m+v).

Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to remove.
void RemoveAllCopies(T item) Remove all items equivalent to a given value.

The asymptotic complexity of this method is O(n+v*log(v)), where n is the size of the collection and v is the number of views.

Parameters:
item:The value to remove.
T RemoveAt(int i) Remove the item at a specific position of the list. /ThrowsSystem.IndexOutOfRangeException if i is negative or >= the size of the collection.
Returns:The removed item.
Parameters:
i:The index of the item to remove.
T RemoveFirst() Remove one item from the front of the list. /ThrowsC5.NoSuchItemException if this list is empty.
Returns:The removed item.
void RemoveInterval(int start, int count) Remove all items in an index interval. /ThrowsSystem.IndexOutOfRangeException???.
Parameters:
start:The index of the first item to remove.
count:The number of items to remove.
T RemoveLast() Remove one item from the back of the list. /ThrowsC5.NoSuchItemException if this list is empty.
Returns:The removed item.
void RetainAll<U>(IEnumerable<U> items) Remove all items not in some other collection from this one, taking multiplicities into account.

The asymptotic running time complexity of this method is O(n+m+v*log(v)), where n is the size of this collection, m is the size of the items collection and v is the number of views. The method will temporarily allocate memory of size O(m+v). The stated complexitiy holds under the assumption that the itemequalityComparer of this list is well-behaved.

Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to retain.
void Reverse() Reverse the list so the items are in the opposite sequence order.
bool SequencedEquals(ISequenced<T> that)
Returns:
Parameters:
that:
void Shuffle() Randomly shuffle the items of this list.

Will invalidate overlapping views???

void Shuffle(System.Random rnd) Shuffle the items of this list according to a specific random source.

Will invalidate overlapping views???

Parameters:
rnd:The random source.
F IList<T> Slide(int offset) Slide this list view along the underlying list.
Throws
NotAViewException if this list is not a view.
System.ArgumentOutOfRangeException if the operation would bring either end of the view outside the underlying list.
Parameters:
offset:The signed amount to slide: positive to slide towards the end.
F IList<T> Slide(int offset, int size) Slide this list view along the underlying list, perhaps changing its size.
Throws
NotAViewException if this list is not a view.
System.ArgumentOutOfRangeException if the operation would bring either end of the view outside the underlying list.
Parameters:
offset:The signed amount to slide: positive to slide towards the end.
size:The new size of the view.
void Sort() Sort the items of the list according to the default sorting order for the item type T, as defined by the Comparer[T] class. (Comparer<T>). The sorting is stable.
Throws
System.InvalidOperationExceptionif T is not comparable
void Sort(System.Collections.Generic.IComparer<T> c) Sort the items of the list according to a specific sorting order. The sorting is stable.
Parameters:
c:The comparer defining the sorting order.
IList<T> Span(IList<T> otherView)

Returns null if otherView is strictly to the left of this view

Throws
IncompatibleViewExceptionIf otherView does not have the same underlying list as this
Returns:
Parameters:
otherView:
bool TrySlide(int offset)
Returns:
Parameters:
offset:
bool TrySlide(int offset, int size)
Returns:
Parameters:
offset:
size:
ICollectionValue<T> UniqueItems()
Returns:
bool UnsequencedEquals(ICollection<T> that)
Returns:
Parameters:
that:
bool Update(T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection to with a binary copy of the supplied value. Will update a single item.
Returns:True if the item was found and hence updated.
Parameters:
item:Value to update.
bool Update(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
P void updatecheck() Check if it is valid to perform updates and increment stamp of underlying if this is a view.

This method should be called in every public modifying methods before any modifications are performed.

Throws
System.InvalidOperationException if check fails.
bool UpdateOrAdd(T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection to with a binary copy of the supplied value; else add the value to the collection.
Returns:True if the item was found and updated (hence not added).
Parameters:
item:Value to add or update.
bool UpdateOrAdd(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
IList<T> View(int start, int count) Create a list view on this list.
Throws
System.ArgumentOutOfRangeException if the start or count is negative
System.ArgumentException if the range does not fit within list.
Returns:The new list view.
Parameters:
start:The index in this list of the start of the view.
count:The size of the view.
IList<T> ViewOf(T item) Create a list view on this list containing the (first) occurrence of a particular item.
Throws
System.ArgumentException if the item is not in this list.
Returns:The new list view.
Parameters:
item:The item to find.